376. 摆动序列

Similar Question

Solution Tips

错误方案: 回溯

var wiggleMaxLength = function(nums) {
    // 有点类似于单调的问题
    // 直接算出差值序列就好, 然后 count 一下统计即可
    // if (nums.length === 1) {
    //     return 1;
    // };

    // if (nums.length === 2) {
    //     return nums[0] === nums[1] ? 1 : 2;
    // }

    // let count = 0;
    let res = 0;

    // for (let i = 2; i < nums.length; i++) {
    //     if ((nums[i] - nums[i - 1]) * (nums[i - 1] - nums[i - 2]) < 0) {
    //         count++;
    //         res = Math.max(res, count)
    //     }
    //     else {
    //         // 同向了, 清零
    //         count = 0;
    //     }
    // }
    // 子序列, 还得贪心的去寻找下一个符合摆动方向的数字?
    // 从每个数字出发, 去贪心的构造一次. 这样能避免 1 17 99 98 100 97
    // 我怎么感觉可以用回溯法来做, 就是二元思路, 要不要带上 17
    // 为什么这里贪心的构造就可以得到最优解呢?
    // 按找回溯法走吧, 暴力也得写出来才行
    backtracking([], 0)
    function backtracking(chosen, i) {
        if (i === nums.length) {
            return;
        }

        // 目前的情况能构造出的最大长度, 不会超过 res 可提前返回
        if (chosen.length + nums.length - i <= res) {
            return;
        }

        const n = chosen.length;
        if (n < 2) {
            // 只要不相等就可以选择
            if (nums[i] !== chosen[n - 1]) {
                chosen.push(nums[i]);
                res = Math.max(res, chosen.length)
                backtracking(chosen, i + 1);
                // 不选择也是ok的
                chosen.pop();
                backtracking(chosen, i + 1);
                return;
            }
        }
        const lastTwo  = chosen[n - 1] - chosen[n - 2];
        if ((nums[i] - chosen[n - 1]) * lastTwo < 0) {
            // 二元思路, 子序列, 越是前面的数, 越是有可能构造出最长的序列, 所以需要提前返回一下 dfs 构造
            chosen.push(nums[i]);
            res = Math.max(res, chosen.length)
            backtracking(chosen, i + 1);
            chosen.pop();
        }
        // 没有选择的 case
        backtracking(chosen, i + 1);
    }
    // 暴力法超时了, 还是得从局部到全局. 对于这个子序列而言, 最长的是这么多, 要么选就是这么多, 要么不选整个跳过
    // 有重复计算的地方, 不论 17 选还是不选, 后面的连续序列中最长的都是一样的
    // 而17如果能选, 那么一定比不选要长
    // 要怎么保证去除掉某个数之后, 不会构成更长的子序列呢?

    return res;
};

console.log(wiggleMaxLength([1,17,5,10,13,15,10,5,16,8]))

从回溯的思路去思考问题, 很容易陷入动态规划与回溯结合的思路中, 但是却写不出代码

方案一: 贪心

观察这个序列可以发现，我们不断地交错选择「峰」与「谷」，可以使得该序列尽可能长。因为剔除掉一个峰或者谷之后, 选择的过渡元素只能成为被剔除的峰或谷, 不可能带来更多的峰或谷

这样，我们只需要统计该序列中「峰」与「谷」的数量即可（注意序列两端的数也是「峰」或「谷」），但需要注意处理相邻的相同元素。

在实际代码中，我们记录当前序列的上升下降趋势。每次加入一个新元素时，用新的上升下降趋势与之前对比，如果出现了「峰」或「谷」，答案加一，并更新当前序列的上升下降趋势。

var wiggleMaxLength = function(nums) {
    const n = nums.length;
    if (n < 2) {
        return n;
    }
    let prevdiff = nums[1] - nums[0];
    let ret = prevdiff !== 0 ? 2 : 1;
    for (let i = 2; i < n; i++) {
        const diff = nums[i] - nums[i - 1];
        if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
            ret++;
            prevdiff = diff;
        }
    }
    return ret;
};

方案三: Dp

分析

可以通过删除元素构造，删除得最少的子序列最长

初始化分析： 只有一个元素的序列也是摆动序列. 有两个元素的序列，只要两个元素不相等，就是摆动序列，两个元素的相对大小决定了摆动的方向

转换视角： 如果波动相同，就和上一轮的最优情况一致，否则就等于上一轮长度的 +1

实现

  var wiggleMaxLength = function (nums) {
    let n = nums.length;
    if (n < 2) {
      return n;
    }
    let wiggle = ''
    let current = ''
    let T = []
    T[0] = 1
    for (let i = 1; i < n; i++) {
      if (nums[i] > nums[i - 1]) {
        current = 'up'
      } else if (nums[i] < nums[i - 1]) {
        current = 'down'
      } else {
        // current = 'equal'
        // 不改变current的值就正好
      }
      // 如果波动相同，最优情况就是T[i - 1],如果波动不相同就+1
      T[i] = current === wiggle ? T[i - 1] : T[i - 1] + 1
      wiggle = current
    }
    return T[n-1]
  };

  var wiggleMaxLength = function (nums) {
    let n = nums.length;
    if (n < 2) {
      return n;
    }
    let up = 1;
    let down = 1;
    for (let i = 1; i < n; i++) {
      if (nums[i] > nums[i - 1]) {
        up = down + 1;
      }
      if (nums[i] < nums[i - 1]) {
        down = up + 1;
      }
    }
    return Math.max(up, down);
  };